НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА" ІНСТИТУТ КОМП’ЮТЕРНИХ ТЕХНОЛОГІЙ, АВТОМАТИКИ ТА МЕТРОЛОГІЇ
ДОСЛІДЖЕННЯ МЕТОДІВ МІНІМІЗАЦІЇ І РЕАЛІЗАЦІЇ БУЛЕВИХ ФУНКЦІЙ ІНСТРУКЦІЯ до лабораторної роботи №2а з дисципліни "ЕЛЕМЕНТИ ДИСКРЕТНИХ ПРИСТРОЇВ АВТОМАТИКИ" для студентів базового напряму 6.0914 «Комп'ютеризовані системи, автоматика і управління» та базового напряму 050201 «Системна інженерія» Затверджено на засіданні кафедри комп’ютеризованих систем автоматики Протокол № від Львів - 2009 Дослідження методів мінімізації і реалізації булевих функцій. Інструкція до лабораторної роботи №2а з дисципліни "Елементи дискретних пристроїв автоматики" для студентів базового напрямку 6.0914 «Комп'ютеризовані системи,автоматика і управління» та базового напрямку 050201 «Системна інженерія» усіх форм навчання / Укл. О.С. Вітер, Р.В.Проць – Львів: НУ(ЛП(, 2008, 10с. Укладачі: О.С.Вітер, канд. техн. наук, доц., Р.В.Проць, канд. техн. наук, доц., Відповідальний за випуск: А.Й. Наконечний д.т.н.,проф. Рецензент: проф. З.Р.Мичуда.  Мета роботи: вивчення методів мінімізації булевих функцій за допомогою карт Карно, діаграм Вейча, і за допомогою програми моделюючого типу Workbench (Multisim). Теоретичний вступ Логічну схему, яка реалізує заданий алгоритм перетворення сигналів, можна синтезувати безпосередньо за виразом, поданим у вигляді досконалої диз’юнктивної нормальної форми, тобто диз’юнкцією наборів елементарних кон’юнкцій однакового рангу (ДДНФ), або у вигляді досконалої кон’юнктивної нормальної форми, тобто кон’юнкцією наборів елементарних диз’юнкцій однакового рангу (ДКНФ). Важливим етапом проектування комп'ютерних схем є мінімізація булевих функцій, тобто знаходження таких їх виразів, які мають мінімальну кількість змінних. Мінімізація забезпечує спрощення практичної реалізації цифрових схем і побудови комп'ютеризованих систем. Для мінімізації функцій із числом змінних п ( 6 застосовують карти Карно або діаграм Вейча, які будують у вигляді таблиць з 2n клітинок з розміткою рядків і стовпчиків змінними. У програмі Workbench прийнято позначати змінні буквами алфавіту, а їх заперечення не рискою, а апострофом, тому такі позначення використані і викладі матеріалу інструкції. Карта Карно для функції чотирьох змінних F(A,B,C,D) показана на рис.1. Рядки карти позначені значеннями змінних A, B, а стовпчики — значеннями змінних C, D. Кожна клітинка карти Карно однозначно відповідає одному наборові таблиці істинності для функції чотирьох змінних (рис. 1), або мінтермам цієї функції (рис. 2).

Рис. 1 Рис. 2 При мінімізації для кожного мінтерму, який входить у ДДНФ функції, ставиться одиниця, а інші клітинки не заповнюються. Наприклад, заповнення карти Карно для функції F(A,B,C,D) = A’BC’D’+ABC’D’+ABC’D+A’B’CD+A’B’CD’+A’BCD’+ABCD’+AB’CD’ показано на рис. 3. Мінтерми в сусідніх клітинках карти Карно в рядку (з врахуванням верхніх і нижніх) або в стовпчику (з врахуванням крайніх) розрізняються значенням однієї змінної, що дозволяє виконувати операцію склеювання по цій змінній.

Рис. 3 Рис. 4 Наприклад, на рис. 3 мінтерми A’B’CD і A’B’CD’ відрізняються значенням змінної D, тому вони склеюються по ній і представляються кон'юнкцією трьох змінних A’B’C. Аналогічно для мінтермів A’B’CD’, A’BCD’, ABCD’ і AB’CD’ склеювання відбувається по змінних AB і одержують кон'юнкцію CD’. Аналогічним способом одержують кон'юнкцію BD’ і BC’D’. У результаті мінімізації функції F(A,B,C,D) одержують її мінімальний вираз Р = ABC’ + BD’ + A’B’C + CD’. Правила мінімізації. Мінімізація функкції, представленої або перетвореної у ДДНФ, здійснюється за наступними правилами: Зображають карту Карно для п змінних і роблять розмітку її рядків і стовпчиків. У кожну клітинку таблиці, яка відповідає мінтерму функції, записують одиницю. Склеюванню підлягають прямокутні конфігурації, які заповнені одиницями і містя...